package LeetCode1;

//根据前序和中序遍历还原二叉树
public class Num105 {
    private  int index = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, inorder, 0, preorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        if (left > right) {
            return null;
        }
        if (index == preorder.length) {
            return null;
        }
        //根据先序可以先找到根节点。
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        //中序可以找到根节点，根节点两边分别为左右子树。
        int pos = findOrder(inorder, root.val);
        root.left = buildTreeHelper(preorder, inorder, left, pos - 1);
        root.right = buildTreeHelper(preorder, inorder, pos + 1, right);
        index = 0;
        return root;
    }

    private int findOrder(int[] inorder, int val) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
